#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;
int word_number=0;
struct record{
    string word;
    int time;
};



void is_record (string a,struct record *list){
    int i=0;
    for(;i<word_number;i++){
        if(list[i].word==a){
            list[i].time++;
            break;
        }
    }
    if(i==word_number){
        list[i].word=a;//record the word
        list[i].time=1;
        word_number++;
    }
}

void rank_word(struct record *list){
//    for(int j=1;j<=word_number;j++){
//    for(int m=1;m<=word_number;m++){
//        for(int i=0;i<word_number-1;i++){
//            if(list[i].time<list[i+1].time){
//                struct record t=list[i];
//                list[i]=list[i+1];
//                list[i+1]=t;
//            }
//            else if(list[i].time==list[i+1].time){
//                if(list[i].word>list[i+1].word){
//                    struct record t=list[i];
//                    list[i]=list[i+1];
//                    list[i+1]=t;
//                }
//                
//            }
//        }}
//    }}不要使用冒泡排序，复杂度太高
    
    for(int i=0;i<word_number;i++){
        int  k=0;
        string x=list[i].word;
        for(int j=i;j<word_number;j++){
            
            if(list[j].word.compare(x)<=0){
                x=list[j].word;
                k=j;
            }
        }
        struct record t=list[k];
        for(int m=k;m>i;m--)list[m]=list[m-1];
        list[i]=t;
    }//character
    
    for(int i=0;i<word_number;i++){
        int k=0,x=0;
        for(int j=i;j<word_number;j++){
            
            if(list[j].time>x){
                x=list[j].time;
                k=j;
            }
        }
        struct record t=list[k];
        for(int m=k;m>i;m--)list[m]=list[m-1];
        list[i]=t;
    }//frequency


}//先按照字典序，再按词频，结果保持正确


int main(){
    ifstream in;
    ofstream out;
    stringstream ss;
    string buf;//save the line
    
    struct record wordlist[150000];   
    string a;//the string in the text


    in.open("ted");//open the file
    while(getline(in,buf)){
        ss <<buf;
        
        while( ss >> a){
            if(a[0]<'a')a[0]+=32;//change capital to lower case 
            is_record(a,wordlist);
              
        }
        ss.clear();//加了这一步就对，不加会有问题,我不清楚是怎么回事
    }
    rank_word(wordlist);
    out.open("word_rank");
    for(int m=0;m<word_number;m++)
        out<<wordlist[m].word<<"  "<<wordlist[m].time<<endl;
    in.close();
    out.close();
    cout<<word_number;
    return 0;
    
}
